package lc;
import java.util.Stack;

import org.junit.*;
public class Ex402 {
    class Solution {

        /* 
        示例 1 ：

输入：num = "1432219", k = 3
输出："1219"
解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。
示例 2 ：

输入：num = "10200", k = 1
输出："200"
解释：移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
示例 3 ：

输入：num = "10", k = 2
输出："0"
解释：从原数字移除所有的数字，剩余为空就是 0 。

        */

        /* 
            对于两个数位相同的数字，他们的大小在于第一个不同的数字。
            如果能保证保留(n - k)个数字的情况下，前面的数字越小越好，而不太需要关注后面的数字
            因为1999也小于2000
        */
        public String removeKdigits(String num, int k) {
            //丢弃k个等于保留len-k个，保留的依据是当前数字大小大于单调栈栈顶
            /* 
                0,1,2,3 4

                "112"
                1
                BUG:最后一位最大就无法解决
            */
            char[] cs = num.toCharArray();
            Stack<Character> stack = new Stack<>();
            int total = cs.length - k, len = cs.length;
            for (int i = 0; i < len; i++) {
                while (!stack.isEmpty() && stack.peek() > cs[i]) {
                    if (k == 0) { //已经不足了，不能再删了
                        break;
                    }
                    stack.pop();
                    k--; //丢弃了一个
                }
                stack.push(cs[i]);
                total--;
            }
            StringBuffer sb = new StringBuffer();
            while (!stack.isEmpty()) {
                sb.insert(0, stack.pop());
            }
            int idx = 0;

            for (int i = 0; i < sb.length(); i++) {
                if (sb.charAt(i) == '0') idx++;
                else break;
            }
            return sb.substring(idx);
        }

        public String removeKdigits2(String num, int k) {
            //丢弃k个等于保留len-k个，保留的依据是当前数字大小大于单调栈栈顶
            /* 
                0,1,2,3 4

                "112"
                1
                BUG:最后一位最大就无法解决
            */
            char[] cs = num.toCharArray();
            StringBuilder stack = new StringBuilder();
            int total = cs.length - k, len = cs.length, t;
            if (total == 0) return "0";
            for (int i = 0; i < len; i++) {
                while ((t = stack.length()) > 0 && stack.charAt(t - 1) > cs[i]) {
                    if (k == 0) break;
                    //删除最后一个
                    stack.setLength(t - 1);
                    k--;
                }
                stack.append(cs[i]);
            }
            String res = stack.substring(0, total);
            int start = 0;
            while (start < res.length() && res.charAt(start) == '0') {
                start++;
            }
            res = res.substring(start);
            return res.isEmpty() ? "0" : res;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        System.out.println(s.removeKdigits2("100", 1));        
    }
}